package com.ljy.my_study.lintcode.快速幂;
/** 
* @author James
* @date 2018年9月29日 
*/
public class TestMain {
//	描述
//	计算an % b，其中a，b和n都是32位的非负整数。
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	例如 231 % 3 = 2
//
//	例如 1001000 % 1000 = 0
//
//	挑战
//	O(logn)
	public static void main(String[] args) {
//		System.out.println((3*3*3*3*3)%7);
		System.out.println(111456*111456%12345);
		System.out.println(11145L*11145L%12345);
		System.out.println(fastPower(11,123898,12345));
	}
	
	public static int fastPower(int a, int b, int n) {
		return (int)fastPower((long)a,(long)b,(long)n);
	}
	
	/**
     * @param a: A 32bit integer
     * @param b: A 32bit integer
     * @param n: A 32bit integer
     * @return: An integer
     */
	public static long fastPower(long a, long b, long n) {
		if(n==0) {
			System.out.println("--------------------");
			System.out.println(1%b);
			return 1%b;
		}
		if(n==1) {
			System.out.println("--------------------");
			System.out.println(a%b);
			return a%b;
		}
		if(n==2) {
			System.out.println("--------------------");
			System.out.println(a%b);
			System.out.println(((a%b)*(a%b))%b);
			return ((a%b)*(a%b))%b;
		}
		if(n%2==1) {
			return (fastPower(fastPower(a,b,2),b,n/2)*fastPower(a,b,1))%b;
		}else {
			return fastPower(fastPower(a,b,2),b,n/2);
		}
	}
}
